class Node:  
    """默认构造函数"""  
    def __init__(self, value = None, next_node=None):  
        self.value = value    # 节点的值  
        self.next = next_node # 指向下一个节点的引用 
    

class LinkedList:  
    """定义链表"""  
    def __init__(self):  
        self.head = None # 链表的头节点 

    # 头插  
    def push_front(self, value):  
        """在链表头部插入一个新节点"""  
        new_node = Node(value)  
        new_node.next = self.head # 新节点的 next 指向当前头节点  
        self.head = new_node      # 更新头节点为新节点  
  
    # 头删  
    def pop_front(self):  
        """删除链表头部的节点并返回其值"""  
        if self.head is None:  
            raise IndexError("Cannot pop from an empty linked list.")  
        res = self.head.value      # 获取要删除节点的值  
        self.head = self.head.next # 更新头节点为下一个节点  
        return res  
  
    # 尾插  
    def push_back(self, value):  
        """在链表尾部插入一个新节点"""  
        new_node = Node(value)  
        if self.head is None:    # 如果链表为空，新节点成为头节点  
            self.head = new_node  
        else:  
            curr = self.head     # 遍历到链表尾部
            while curr.next is not None:    
                curr = curr.next  
            curr.next = new_node # 在尾部插入新节点  
  
    # 尾删  
    def pop_back(self):  
        """删除链表尾部的节点并返回其值"""  
        if self.head is None:  
            raise IndexError("Cannot pop from an empty linked list.")  
        if self.head.next is None: # 如果链表只有一个节点  
            res = self.head.value  
            self.head = None       # 清空头节点  
            return res
          
        curr = self.head           # 遍历到倒数第二个节点
        while curr.next.next is not None:    
            curr = curr.next  
        res = curr.next.value      # 获取要删除节点的值  
        curr.next = None           # 删除尾节点  
        return res  
    
    # 查找
    def search(self, target):  
            """查找链表中第一个值为target的节点，并返回其节点对象"""  
            curr = self.head  
            while curr is not None:  
                if curr.value == target:  
                    return curr # 返回找到的节点对象  
                curr = curr.next  
            return None         # 如果未找到，返回None
  
    # 修改  
    def update(self, old_value, new_value):    
        """修改链表中第一个值为old_value的节点的值为new_value，并返回是否成功修改"""    
        node = self.search(old_value) # 查找节点    
        if node is not None:    
            node.value = new_value    
            return True               # 修改成功    
        return False                  # 未找到要修改的节点 
  
    # 打印  
    def print_list(self):  
        """打印链表中的所有节点值"""  
        curr = self.head  
        while curr is not None:  
            print(f"{curr.value}->", end="")  
            curr = curr.next  
        print("None")  
  
  
    # 移除元素  
    def remove_elements(self, val):  
        """删除链表中所有值等于 val 的节点"""  
        # 头节点值等于 val
        # 头删，直到头节点不等于 val或链表为空
        while self.head is not None and self.head.value == val:  
            self.pop_front()  


        # 初始化 prev 和 curr 指针  
        prev = None  
        curr = self.head  
          
        while curr is not None:  
            # 如果当前节点值等于 val  
            # 将前一个节点的 next 引用指向当前节点的下一个节点
            if curr.value == val:  
                if prev is not None:  
                    prev.next = curr.next  
            else:  
                # 更新 prev 指针  
                prev = curr  
            # 移动 curr 指针到下一个节点  
            curr = curr.next


# 示例测试  
if __name__ == "__main__":    
    # 创建链表
    l1 = LinkedList() 
    l2 = LinkedList()  
    l3 = LinkedList() 

    for i in [i + 1 for i in range(6)]:
        l1.push_back(i)
    for i in [1, 1, 2, 1, 3, 4, 5, 1, 7, 9, 1]:
        l2.push_back(i)
    for i in [1]:
        l3.push_back(i)
    
    l1.print_list()
    l1.remove_elements(6)
    l1.print_list()
    print()

    l2.print_list()
    l2.remove_elements(1)
    l2.print_list()
    print()

    l3.print_list()
    l3.remove_elements(1)
    l3.print_list(5)
    print()